最長公用次序列(Longest Common Subsequence，簡稱LCS)是一題經典的面試題目，因為他的解法是一個典型的”二維”動態規劃，大部分比較困難的字串問題都和這個問題使用類似的模式，另外

稍微修改優化一下就能夠用來解決其他問題，所以LCS是很值得掌握的演算法．題目很簡單

給定兩個字串，求他們其中最長的公用次序列

例如給定 str1 = “abcde” str2= “aceb”，則答案是3，他們公用的次序列 為”ace”，長度為3(注意次序列可以斷開)

思考過程

動態規劃的第一步，先確定dp 矩陣的含義

對於兩個字串的動態規劃問題，通常的模式就是使用一個二維的陣列

例如測資 str1 = “babcde” str2= “ace”，dp 矩陣可以畫成這樣

其中dp[i][j]的含義，即是

對於str1[0..i-1] 跟str2[0..j-1]他們的LCS長度

以這個測資來說 dp[2][4] = 2的意義就是．對於”babc”(來自str1)與”ac”(來自str2) 他們的 LCS 長為2，而根據題目，答案就在dp[3][6]．

第二步，確認初始的base case

我們在dp陣列專門填入了一行跟一列為0的，來表示空字串．dp[0][XX]跟dp[XX][0]都填入初始值為0

根據剛剛dp 矩陣 的定義，dp[0][3] = 0 的含義就是，空字串””跟字串”bab”的LCS為何，因為有一個字串是空字串，所以其顯然為0

第三步，狀態轉移方程

這個就是之前動態轉移範本的”選擇”．

我們先將題目的答案訂成 lcs (小寫的)，那麼對於str1跟str2裡面的每個字元，他們可以有什麼選擇呢？

答案其實很簡單，就是這個字元，有沒有在最後答案lcs中

好，我們有”在”跟”不在”兩個選擇了，接下來的問題就變成了

我們怎麼知道 str1[i]，str2[j]在不在最後答案lcs中呢？

很快就能想到，如果某個字元在lcs中，那麼這個字元一定在str1跟str2中．

我們設計轉移函數 dp(i,j) ，其定義為str1[0..i]和str2[0..j]中最長公用子次序的長度

那麼接下來有幾種狀況

1.str1[i] == str2[j]

那這個字元一定會在最後答案lcs中，所以如果我們已經知道 str1[0..i-1]跟str2[0..j-1]的lcs長度，那就再加上現在這個相等的字元，也就是

if(str1[i] == str2[j]){
	dp(i,j) = dp(i-1, j-1)+1
}

1.str1[i] != str2[j]

若這兩個不相等，那這兩個字元中，必有最少一個不存在最後答案lcs中，那要怎麼判斷呢？

很簡單，兩個都試試看吧，可以讓lcs比較長的就是正確的那邊

if(str1[i] != str2[j]){
	dp(i,j) = max(dp(i-1,j),dp(i, j-1))
}

確認好狀態轉移方程後，就能直接寫出寫法

fun longestCommonSubsequence(str1:String,str2:String):Int{
    fun dp(i:Int,j:Int):Int{
        if(i == -1|| j ==-1){//與空字串相比的base case
            return 0
        }
        return if(str1[i] == str2[j]){//兩個字串都有 代表是lcs之一
            dp(i-1,j-1)+1
        }else{//至少有一個不在lcs中，都找找看，誰比較長就選誰
            Math.max(dp(i-1,j),dp(i,j-1))
        }

    }
    return dp(str1.length-1,str2.length-1)
}

這個是暴力解法，不過寫出暴力解法就很接近解答了，我們再來使用db Table來進行狀態壓縮，改善時間複雜度

fun longestCommonSubsequenceWithDpTable(str1: String, str2: String): Int {
    val m = str1.length
    val n = str2.length
    val dpTable: Array<Array<Int>> = Array(m + 1) { Array(n + 1) { 0 } }
    for (i in 1..m) {
        for (j in 1..n) {
            if (str1[i - 1] == str2[j - 1]) {
                dpTable[i][j] = dpTable[i - 1][j - 1] + 1
            } else {
                dpTable[i][j] = Math.max(dpTable[i - 1][j], dpTable[i][j - 1])
            }
        }
    }
    return dpTable[m][n]
}

如何，是不是很簡單呢？